package cxydmmszl.tmp.t10;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 0左边必有 1 的二进制字符串的数量
 * <li style="color: green;">Desc</li>
 * 给定一个整数 n，求由“0”字符和“1”字符组成的长度为n的所有字符串中，
 * 满足“0”字符的左边必有“1”字符的字符串的数量。
 * <br/><br/>备注：<br/>
 * 时间复杂度 O(log<sub>2</sub>n)。额外空间复杂度 O(1)。
 * <li style="color: green;">Input</li>
 * 输入一行，包含一个整数 n（1&le;n&le;2&times;10<sup>7</sup>）。
 * <li style="color: green;">Output</li>
 * 输出一个整数，表示返回的答案，由于字符串的数量巨大，可能会溢出，
 * 请输出对 2<sup>29</sup> 取模后的答案。
 * <li style="color: blue;">Link</li> CD129
 *
 * @author habitplus
 * @since 2021-11-19 10:02
 */
public class Main {

    static final long mod = (1 << 29) - 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        long ans = numStr2(n);
        System.out.println(ans);
    }

    /*
        斐波那契数列变体
     */
    private static long numStr(int n) {
        if (n < 3) return n;

        long f1 = 1;
        long f2 = 2;
        long t;
        while (n-- > 2) {
            t = (f1 + f2) & mod;
            f1 = f2;
            f2 = t;
        }
        return f2;
    }

    public static long numStr2(int n) {
        if (n < 3) return n;

        long[][] base = {{1, 1}, {1, 0}};
        long[][] res = matrixPower(base, n - 2);
        return (2 * res[0][0] + res[1][0]) & mod;
    }

    private static long[][] matrixPower(long[][] m, int p) {
        long[][] res = new long[m.length][m[0].length];
        for (int i = 0; i < res.length; i++) res[i][i] = 1;

        long[][] tmp = m;
        while (p != 0) {
            if ((p & 1) != 0) {
                res = mulMatrix(res, tmp);
            }
            tmp = mulMatrix(tmp, tmp);
            p >>= 1;
        }

        return res;
    }

    private static long[][] mulMatrix(long[][] m1, long[][] m2) {
        int n = m1.length;
        int m = m2[0].length;
        long[][] res = new long[n][m];
        long t;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                t = 0;
                for (int k = 0; k < n; k++) {
                    t = (((m1[i][k] * m2[k][j]) & mod) + t) & mod;
                }
                res[i][j] = t;
            }
        }

        return res;
    }
}
